strlst@ayaya ue6 cat folge.py
#!/usr/bin/env python3

def folge(n):
  if n <= 2:
    return 0
  if n == 3:
    return 1
  else:
    return folge(n-1) + 2 * folge(n-2) + 3 * folge(n-3)

print([folge(n) for n in range(30)])
strlst@ayaya ue6 cat opt_folge.py
#!/usr/bin/env python3

def opt_folge(n):
  f = list()
  for i in range(n + 1):
    f.append(0)
    if i <= 2:
      continue
    if i == 3:
      f[i] = 1
      continue
    f[i] = f[i - 1] + 2 * f[i - 2] + 3 * f[i - 3]
  return f[n]

print([opt_folge(n) for n in range(30)])
strlst@ayaya ue6 time python3 folge.py
[0, 0, 0, 1, 1, 3, 8, 17, 42, 100, 235, 561, 1331, 3158, 7503, 17812, 42292, 100425, 238445, 566171, 1344336, 3192013, 7579198, 17996232, 42730667, 101460725, 240910755, 572024206, 1358227891, 3225008568]
    0m05.36s real     0m05.35s user     0m00.00s system
strlst@ayaya ue6 time python3 opt_folge.py
[0, 0, 0, 1, 1, 3, 8, 17, 42, 100, 235, 561, 1331, 3158, 7503, 17812, 42292, 100425, 238445, 566171, 1344336, 3192013, 7579198, 17996232, 42730667, 101460725, 240910755, 572024206, 1358227891, 3225008568]
    0m00.02s real     0m00.02s user     0m00.00s system
